import sun.nio.cs.ext.MacHebrew;

import javax.swing.*;
import java.util.*;

/**
 * Created by cc
 * Description:
 * User: CZH
 * Date: 2022-11-12
 * Time: 10:37
 */
class Node {
    public char val;
    public Node left;
    public Node right;

    public Node(char val) {
        this.val = val;
    }
}

public class TestBinaryTree {

    //使用穷举的方式创建一棵二叉树
    public Node createTree() {
        Node A = new Node('A');
        Node B = new Node('B');
        Node C = new Node('C');
        Node D = new Node('D');
        Node E = new Node('E');
        Node F = new Node('F');
        Node G = new Node('G');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        return A;
    }

    //前序遍历
    void preOrderTraversal(Node root) {
        if (root == null) return;
        System.out.print(root.val + " ");
        preOrderTraversal(root.left);
        preOrderTraversal(root.right);
    }
    //前序遍历，使用返回list
    public List<Character> preOrderTraversal1(Node root) {
        List<Character> cList = new LinkedList<>();
        if (root == null) return cList;
        cList.add(root.val);

        List<Character> leftList = preOrderTraversal1(root.left);
        cList.addAll(leftList);

        List<Character> rightList = preOrderTraversal1(root.right);
        cList.addAll(rightList);
        return cList;
    }

    //中序遍历
    void inOrderTraversal(Node root) {
        if (root == null) return;
        inOrderTraversal(root.left);
        System.out.print(root.val + " ");
        inOrderTraversal(root.right);
    }

    //后序遍历
    void postOrderTraversal(Node root) {
        if (root == null) return;
        postOrderTraversal(root.left);
        postOrderTraversal(root.right);
        System.out.print(root.val + " ");
    }

    //求结点个数 -遍历思路
    //把每个结点都遍历一次，size一次++
    static int size = 0;
    void getSize1(Node root) {
        if (root == null) return;
        size++;
        getSize1(root.left);
        getSize1(root.right);
    }

    //求结点个数 -子问题思路
    //只判断目前该结点root是否有值，左右子树交给递归解决。
    int getSize2(Node root) {
        if (root == null) return 0;
        int val = getSize2(root.left) + getSize2(root.right) + 1;
        return val;
    }

    //求叶子结点个数 -遍历思路
    //没有左右子树的结点是叶子结点，遍历每一个结点，统计叶子结点
    static int leafSize = 0;
    void getLeafSize1(Node root) {
        if (root == null) return;
        if (root.left == null && root.right == null) leafSize++;
        getLeafSize1(root.left);
        getLeafSize1(root.right);
    }

    //求叶子结点个数 -子问题思路
    //只判断该结点是否是叶子，其它结点交给递归判断。
    int getLeafSize2(Node root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;
        int val = getLeafSize2(root.left) + getLeafSize2(root.right);
        return val;
    }

    //求第K层节点个数
    //子问题思路 -使用递归计算左右子树的节点，然后相加。
    int getKLevelSize(Node root, int k) {
        if (root == null) {
            throw new RuntimeException("k大于二叉树层数 或 根节点为null");
        }
        if (k == 1) return 1;
        int val = getKLevelSize(root.left,k-1) + getKLevelSize(root.right, k-1);
        return val;
    }

    //求二叉树的高度
    //子问题思路 -通过递归求左右子树高度，最后相比 取高者+1.
    //每次遍历都是通过return里面的+1，对子树高度相加。
    //最后左右子树遍历完，二者对比，取高者+1.
    int getHeight(Node root) {
        if (root == null) return 0;
        int leftTree = getHeight(root.left);
        int rightTree = getHeight(root.right);
        return leftTree > rightTree ? (leftTree+1) : (rightTree+1);
    }

    //在root中找val值
    //子问题解决思路 - 只判断该节点是否是val，其它节点交给递归解决。
    //注意最后所有条件不符合，需要返回null
    Node find(Node root, char val) {
        if (root == null) return null;
        if (root.val == val) return root;

        Node ret = find(root.left, val);
        if (ret != null) return ret;

        ret = find(root.right, val);
        if (ret != null) return ret;

        return null;
    }

    //判断两棵树是否相同
    //使用子问题思路解决 -
    // 判断根节点：
    // 1.是否都是null；值是否相同；一个为空 一个不为空；（结构比较，值比较）
    // 2.结构相同，值相同。
    // 其它节点交给递归解决。
    public boolean isSameTree(Node x, Node y) {
        if ((x == null && y != null) || (x != null && y == null)) {
            return false;
        }
        if (x == null && y == null) {
            return true;
        }
        if (x.val != y.val) {
            return false;
        }
        return isSameTree(x.left, y.left) && isSameTree(x.right, y.right);
    }

    //判断sub是否是root的子树。
    //判断root是否null，subRoot是否和root相同
    //不同就递归判断下面的结构，是否和subRoot相同
    public boolean isSubtree(Node root, Node subRoot) {
        if (root == null) return false;
        if (isSameTree(root, subRoot)) return true;
        if (isSubtree(root.left, subRoot)) return true;
        if (isSubtree(root.right, subRoot)) return true;
        return false;
    }

    //判断二叉树的最大深度
    public int maxDepth(Node root) {
        if (root == null) return 0;
        int leftTree = maxDepth(root.left);
        int rightTree = maxDepth(root.right);
        return leftTree > rightTree ? (leftTree+1) : (rightTree+1);
    }

    //判断该二叉树是否是平衡二叉树
    //判断根节点的左右子树是否平衡，算出左右高度相减绝对值小于等于1
    //接着继续计算左右子树的左右子树。
    public boolean isBalanced1(Node root) {
        if (root == null) return true;
        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);
        return Math.abs(leftHeight-rightHeight)<=1
                && isBalanced1(root.left) && isBalanced1(root.right);
    }

    //判断该二叉树是否是平衡二叉树 - O(N)解法
    //上一个解法，每个节点都需要去求深度，导致开销过大。
    //O(N)解法，能遍历节点的中途，判断这部分二叉树是否平衡，不需要全部节点都遍历。
    public int maxDepth2(Node root) {
        if (root == null) return 0;
        //递归判断左右子树的高度。
        int leftHeight = maxDepth2(root.left);
        int rightHeight = maxDepth2(root.right);

        //高度不可能是负数，负数表示不平衡
        if (leftHeight >= 0 && rightHeight >= 0 &&
                //条件成立，说明是平衡的结点
                Math.abs(rightHeight - leftHeight) <= 0) {
            //返回结点的最大左右子节点，+1加上自己这个结点。
            return Math.max(rightHeight, leftHeight) + 1;
        }else {
            return -1;
        }
    }
    public boolean isBalanced2(Node root) {
        return maxDepth2(root) >= 0;
    }


    //对称二叉树
    public boolean isSymmetricChild(Node leftTree, Node rightTree) {
        //判断左右子树结构是否相同
        if (leftTree == null && rightTree != null ||
                leftTree != null && rightTree == null) {
            return false;
        }
        //判断左右子树是否为 null
        if (leftTree == null && rightTree == null) {
            return true;
        }
        //判断左右子树数值是否相同
        if (leftTree.val != rightTree.val) {
            return false;
        }
        //左右对称，那么递归解决左树和右树是否对称。
        return isSymmetricChild(leftTree.left, rightTree.right) &&
                isSymmetricChild(leftTree.right, rightTree.left);
    }
    //针对不同情况：传递根节点 还是根的左右树
    public boolean isSymmetric(Node root) {
        if (root == null) return false;
        return isSymmetricChild(root.left, root.right);
    }

    //层序遍历二叉树1
    //使用链式队列存储，不为空就入队列
    public void levelOrderTraversal(Node root) {
        if (root == null) return;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node top = queue.poll();
            System.out.print(top.val + " ");
            if (top.left != null) {
                queue.offer(top.left);
            }
            if (top.right != null) {
                queue.offer(top.right);
            }
        }
    }

    //层序遍历二叉树2
    //使用 List<List<Character>> 存储层序遍历的二叉树。
    public List<List<Character>> levelOrder(Node root) {
        //创建对应类型，如果根节点为空，直接返回
        List<List<Character>> ret = new ArrayList<>();
        if (root == null) return ret;
        //使用队列，进行层序遍历
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            //记录队列所剩的结点个数，用于内循环
            int size = queue.size();
            //存储内循环弹出队列的结点
            List<Character> list = new ArrayList<>();

            while (size > 0) {
                //弹出，存储
                Node top = queue.poll();
                list.add(top.val);
                //查看弹出结点的左右结点是否存在
                if (top.left != null) {
                    queue.offer(top.left);
                }
                if (top.right != null) {
                    queue.offer(top.right);
                }
                //本次循环结束，结点-1
                size--;
            }
            //内循环结束，把数据添加到 List<List<Character>>
            ret.add(list);
        }
        return ret;
    }

    //判断一棵树是否二完全二叉树
    boolean isCompleteTree(Node root) {
        if (root == null) return true;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        //把节点都入队列。遇到NULL就停止。
        while (!queue.isEmpty()) {
            Node top = queue.poll();
            if (top == null) {
                break;
            }
            queue.offer(top.left);
            queue.offer(top.right);
        }
        //查看队头是否是null，不是就表示不是完全二叉树。
        while (!queue.isEmpty()) {
            Node top = queue.peek();
            if (top != null) {
                return false;
            }
            queue.poll();
        }
        return true;
    }

    //二叉树的创建 abc##de#g##f###
    static int i = 0;
    public Node createTreeForString(String str) {
       Node root = null;
        if (str.charAt(i) != '#') {
            root = new Node(str.charAt(i));
            i++;
            root.left = createTreeForString(str);
            root.right = createTreeForString(str);
        }else {
            i++;
        }
        return root;
    }

    //中序遍历打印二叉树
    public void inorder(Node root) {
        if (root == null) return;
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }

    //找公共祖先
    public Node lowestCommonAncestor(Node root, Node p, Node q) {
        if (root == null) return null;
        //p和q相等，返回根节点
        if (root == p || root == q) {
            return root;
        }
        //递归去找左右子树，是否存在p和q。
        Node leftTree = lowestCommonAncestor(root.left, p, q);
        Node rightTree = lowestCommonAncestor(root.right, p, q);
        //左右子树各自有p和q，返回根节点
        if (leftTree != null && rightTree != null) {
            return root;
        }
        //一边子树存在，一边不存在，返回子树的根节点
        if (leftTree == null && rightTree != null) {
            return leftTree;
        }
        if (leftTree != null && rightTree == null) {
            return rightTree;
        }
        //都没有p和q，返回null
        if (leftTree == null && rightTree == null) {
            return null;
        }
        //上述条件都不满足，返回null
        return null;
    }

    //把搜索二叉树转换成有序双向链表
    Node prev = null;   //需要前驱节点，方便链接链表
    public void ConvertChild(Node pCur) {
        if (pCur == null) return;

        //搜索二叉树中序遍历，就可以转换成有序双向链表
        ConvertChild(pCur.left);

        //pCur当前节点的left置为null
        pCur.left = prev;
        if (prev != null) {
            //前驱节点，链接上当前节点
            prev.right = pCur;
        }
        //双向链接完毕，前驱节点移动到当前节点pCur上。
        prev = pCur;

        //搜索二叉树中序遍历，就可以转换成有序双向链表
        ConvertChild(pCur.right);
    }

    public Node Convert(Node pRootOfTree) {
        if (pRootOfTree == null) return null;
        //改变结构
        ConvertChild(pRootOfTree);
        //记录容易一个节点，去查找双向链表的头节点
        Node head = pRootOfTree;
        while (head.left != null) {
            head = head.left;
        }
        return head;
    }

    //通过前序遍历和中序遍历构造二叉树
    public int preIndex = 0;    //记录根节点坐标
    public Node buildTreeChildPre(char[] preOrder, char[] inOrder, int inBegin, int inEnd) {
        if (inBegin > inEnd) {  //没有左右子树 或者 输入不合理
            return null;
        }
        //先序遍历，首元素就是根节点
        Node root = new Node(preOrder[preIndex]);
        //找到根节点在中序遍历中的位置
        int rootIndex = findInorderIndex(inOrder, inBegin, inEnd, preOrder[preIndex]);
        preIndex++;
        //通过遍历，完成构造左右子树
        root.left = buildTreeChildPre(preOrder, inOrder, inBegin, rootIndex-1);
        root.right = buildTreeChildPre(preOrder, inOrder, rootIndex+1, inEnd);
        return root;
    }

    //根据先序遍历，找到根节点在中序遍历的坐标
    public int findInorderIndex(char[] inorder, int inBegin, int inEnd, char key) {
        //循环查找
        for (int i = inBegin; i <= inEnd; i++) {
            if (key == inorder[i]) {
                return i;
            }
        }
        return -1;
    }


    //通过后序和中序遍历序列构造二叉树
    public int postIndex = 0;   //后序序列的根节点坐标
    public Node buildTree(char[] inOrder, char[] postOrder) {
        if (inOrder == null || postOrder == null) {
            return null;
        }
        //后序序列的根节点坐标
        postIndex = postOrder.length - 1;
        //传递准备好的数据
        return buildTreeChildPost(postOrder, inOrder, 0, inOrder.length - 1);
    }
    //
    public Node buildTreeChildPost(char[] postOrder, char[] inOrder, int inBegin, int inEnd) {
        if (inBegin > inEnd) {  //左右子树不存在返回 null
            return null;
        }
        //后序序列最后元素就是根节点 root
        Node root = new Node(postOrder[postIndex]);
        //在中序序列中找到根节点坐标
        int rootIndex = findInorderIndex(inOrder, inBegin, inEnd, postOrder[postIndex]);
        //递归的结束条件，慢慢减少
        postIndex--;
        //后序，先右再左构造子树
        root.right = buildTreeChildPost(postOrder, inOrder, rootIndex + 1, inEnd);
        root.left = buildTreeChildPost(postOrder, inOrder, inBegin, rootIndex - 1);
        return root;
    }


    //二叉树创建带括号的字符串
    /*
输入：root = [1,2,3,4]
输出："1(2(4))(3)"
解释：字符串应该是"1(2(4))(3)" 。
    * */
    public void tree2strChild(Node t, StringBuilder sb) {
        if (t == null) return;
        sb.append(t.val);

        if (t.left == null) {
            if (t.right == null) {
                return;
            }else {
                sb.append("()");
            }
        }else {
            sb.append("(");
            tree2strChild(t.left, sb);
            sb.append(")");
        }

        if (t.right == null) {
            return;
        }else {
            sb.append("(");
            tree2strChild(t.right, sb);
            sb.append(")");
        }
    }

    public String tree2str(Node root) {
        if (root == null) return null;
        StringBuilder sb = new StringBuilder();
        tree2strChild(root, sb);
        return sb.toString();
    }

    //前序遍历非递归 -利用栈来完成
    void preOrderTraversalNor(Node root) {
        if (root == null) return;
        Stack<Node> stack = new Stack<>();
        Node cur = root; //根节点入栈
        //外层控制右子树的入栈
        while (cur != null || !stack.empty()) {
            //内层控制左子树的入栈
            while (cur != null) {
                stack.push(cur);
                System.out.print(cur.val + " ");
                cur = cur.left;
            }
            Node top = stack.pop();
            cur = top.right;
        }
    }

    //中序遍历非递归写法 -左根右，变换顺序即可
    void inOrderTraversalNor(Node root) {
        if (root == null) return;
        Stack<Node> stack = new Stack<>();
        Node cur = root;

        while (cur != null || !stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            Node top = stack.pop();
            System.out.print(top.val + " ");
            cur = top.right;
        }
    }

    //后序遍历非递归写法 -左右根
    void post(Node root) {
        if (root == null) return;
        Stack<Node> stack = new Stack<>();
        Node prev = null;
        Node cur = root;
        while (cur != null || !stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.peek();
            if (cur.right == null || cur.right == prev) {
                System.out.print(cur.val + " ");
                stack.pop();
                prev = cur;
                cur = null;
            }else {
                cur = cur.right;
            }
        }
    }



    void postOrderTraversalNor1(Node root) {
        if (root == null) return;
        Node prev = null;   //用于记录打印过的节点
        Stack<Node> stack = new Stack<>();
        Node cur = root;

        while (cur != null || !stack.empty()) {
            //先把所有左子树的节点入栈
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            //取栈顶节点查看
            cur = stack.peek();
            //如果该节点没有右子树或者右子树被prev标记过
            //那么表示可以直接打印该节点
            if (cur.right == null || cur.right == prev) {
                stack.pop();
                System.out.print(cur.val + " ");
                prev = cur; //记录被打印过的节点
                cur = null; //置为空，目的为了查看下一个节点是否有右子树
            //右子树没有被操作过，则把右子树入栈
            }else {
                cur = cur.right;
            }
        }
    }






}
